package com.douma.第15天;

import java.util.Scanner;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class 分糖果 {

    /*
    题目 1：分糖果
    小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。
    当糖果不能平均分配时，小明可以选择从糖果盒中 (假设糖果盒中糖果足够) 取出一个糖果或放回一个糖果。
    小明最少需要多少次 (取出、放回和平均分配均记为一次)，能将手中糖果分至只剩一颗。
    输入一个整数，表示总的糖果数，总的糖果数小于 10000000000

    示例 1：
    输入
    15

    输出
    5

    说明：最少分至一颗糖的次数是 5，
    第一次：15 + 1 = 16
    第二次：16 / 2 = 8
    第三次：8 / 2 = 4
    第四次：4 / 2 = 2
    第五次：2 / 2 = 1
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int res = 0;

        while (n > 1) {
            res++;
            if (n % 2 == 0) {
                // 可以平均分
                n = n / 2;
            } else {
                // 不能平均分，那要么取出一个，要么增加一个
                // 如果增加一个糖果后，均分后的一半可以再次均分的话，那么就增加一个糖果
                if ((n + 1) / 2 % 2 == 0) {
                    n++;
                } else {
                    // 取出一个糖果
                    n--;
                }
            }
        }
        System.out.println(res);

        sc.close();
    }
}
